package com.lishem.top100._08tree;

import com.lishem.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/
 * <p>
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * <p>
 * 展开后的单链表应该同样使用 TreeNode，
 * <p>
 * 其中right子指针指向链表中下一个结点，而左子指针始终为 null 。
 * <p>
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 */
public class _11LetCode114_二叉树展开为链表 {

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        stack.push(root);
        while (!stack.isEmpty()){
            root = stack.pop();
            if (pre != null){
                pre.left = null;
                pre.right = root;
            }
            pre = root;
            if (root.right != null){
                stack.push(root.right);
            }
            if (root.left != null){
                stack.push(root.left);
            }
        }
    }

    // 基础做法，先序递归遍历，然后连接
    public void flatten2(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preOrderTraversal(root, list);
        for (int i = 1; i < list.size(); i++) {
            list.get(i - 1).right = list.get(i);
            list.get(i - 1).right = null;
        }
    }

    private void preOrderTraversal(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        preOrderTraversal(root.left, list);
        preOrderTraversal(root.right, list);
    }

    // 基础做法，先序迭代遍历，然后连接
    public void flatten1(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            list.add(root);
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).right = list.get(i + 1);
            list.get(i).left = null;
        }
    }

    public static void main(String[] args) {
        _11LetCode114_二叉树展开为链表 sol = new _11LetCode114_二叉树展开为链表();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        sol.flatten1(root);
        System.out.println("-");
    }
}
